"""DisjointSets.py
Description:
Based on details provided by: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
and modified based on notes of CS 473 Algorithms course by University of Illinois.
Finally adapted to Kruskal problem presented by course 75.29 Teoria de Algoritmos on
University of Buenos Aires.


Authors:
Garay, Ignacio
Liguori, Ariel
Musumeci, Pablo
"""

valueNodeDict = {}

class Node():
	'''Represents a node in a tree, using rank.'''
	def __init__(self, value, parent, rank):
		self.value = value
		self.parent = parent
		self.rank = rank
		valueNodeDict[value] = self

	def __str__(self):
		return str(value)

class Universe():
	'''All sets will belong to the Universe.'''
	def __init__(self):
		self.sets = [] #list of all root nodes
	
	def addSet(self, root):
		self.sets.append(root)
	
U = Universe()

def internalFindSet(x):
	'''Find the root of the tree that contains this node, uses 
	   path compression at every stage.'''
	if x.parent is not x:
		x.parent = internalFindSet(x.parent)
	return x.parent

def MakeSet(x):
	'''Make a new node whose parent is itself, as some bibliography
	   mentions a singleton instance of x.'''
	a = Node(x, None, 0) # O(1)
	a.parent = a #O(1)
	U.addSet(a) #O(1) = Amortized Worst Case

def FindSet(x):
	'''Returns the root of the tree which contains this x'''
	x_node = valueNodeDict[x] #O(n)
	return internalFindSet(x_node)

def Union(x, y):
	'''Union by rank based on pseudocode defined on beginning notes, unites
	   x and y destructively, updates ranks.'''
	x_set = FindSet(x)
	y_set = FindSet(y)

	if x_set.rank > y_set.rank:
		y_set.parent = x_set
	else:
		x_set.parent = y_set
		if x_set.rank == y_set.rank:
			y_set.rank += 1